﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0128_PostorderTraversal : IAlgorithm
    {
        // 145. 二叉树的后序遍历

        // 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

        public void Test()
        {
        }

        // 算法
        public IList<int> PostorderTraversal(TreeNode root)
        {
            var res = new List<int>();
            if (root == null)
                return res;
            Helper(root, res);
            return res;
        }
        private void Helper(TreeNode root, List<int> res)
        {
            if (root == null)
                return;
            Helper(root.left, res);
            Helper(root.right, res);
            res.Add(root.val);
        }

        // 非递归
        public IList<int> PostorderTraversal1(TreeNode root)
        {
            var res = new List<int>();
            if (root == null)
                return res;
            var stack = new Stack<TreeNode>();
            TreeNode prev = null;
            while (root != null || stack.Count>0)
            {
                while (root != null)
                {
                    stack.Push(root);
                    root = root.left;
                }
                root = stack.Pop();
                if (root.right == null || root.right == prev)
                {
                    res.Add(root.val);
                    prev = root;
                    root = null;
                }
                else
                {
                    stack.Push(root);
                    root = root.right;
                }
            }
            return res;
        }
    }
}
